package jzOffer;

import java.util.HashMap;
import java.util.Map;

public class Num55of2 {
    //1.递归
//    public boolean isBalanced(TreeNode root) {
//        if(root==null) return true;
//        int count=Math.abs(maxDepth(root.left)-maxDepth(root.right));
//        if(count>1){
//            return false;
//        }
//        return isBalanced(root.left) && isBalanced(root.right);
//
//    }
//    public int maxDepth(TreeNode root) {
//        if(root==null) return 0;
//        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
//    }

    //2.使用Map优化递归效率
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        Map<TreeNode,Integer> map=new HashMap<>();
        int leftHeight=0;
        int rightHeight=0;
        if(map.containsKey(root.left)){
            leftHeight=map.get(root.left);
        }else{
            leftHeight=maxDepth(root.left);
            map.put(root.left,leftHeight);
        }

        if(map.containsKey(root.right)){
            rightHeight=map.get(root.right);
        }else{
            rightHeight=maxDepth(root.right);
            map.put(root.right,rightHeight);
        }
        int count=Math.abs( leftHeight-rightHeight);
        if(count>1){
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);

    }
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
    }
}
